#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int dfn[N], low[N], deg[N], sz[N], scc[N], dfncnt, scccnt;
bool instk[N];
vector<int> adj[N], sccadj[N];
stack<int> s;
int f[N], g[N], used[N];
int n, m, x;
void tarjan(int u) {
  dfn[u] = low[u] = ++dfncnt;
  s.push(u);
  instk[u] = true;
  for (auto v : adj[u]) {
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (instk[v]) {
      low[u] = min(low[u], dfn[v]);
    }
  }
  if (dfn[u] == low[u]) {
    scccnt++;
    int k = -1;
    do {
      k = s.top();
      s.pop();
      sz[scccnt]++;
      instk[k] = false;
      scc[k] = scccnt;
    } while (k != u);
  }
}
int main() {
  cin >> n >> m >> x;
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
  }
  for (int i = 1; i <= n; ++i)
    if (!dfn[i]) tarjan(i);

  for (int u = 1; u <= n; ++u) {
    f[u] = sz[u];
    g[u] = 1;
    for (auto v : adj[u]) {
      if (scc[u] == scc[v]) continue;
      sccadj[scc[u]].push_back(scc[v]);
    }
  }
  for (int u = scccnt; u >= 1; --u) {
    for (int v : sccadj[u]) {
      if (used[v] == u) continue;
      used[v] = u;
      if (f[v] < f[u] + sz[v]) {
        f[v] = f[u] + sz[v];
        g[v] = g[u];
      } else if (f[v] == f[u] + sz[v]) {
        g[v] += g[u];
        g[v] %= x;
      }
    }
  }
  int ans = 0, tmp = 0;
  for (int i = 1l; i <= scccnt; ++i) {
    if (f[i] > ans) {
      ans = f[i];
      tmp = g[i];
    } else if (f[i] == ans) {
      tmp += g[i];
      tmp %= x;
    }
  }
  cout << ans << endl << tmp << endl;
}
